#include"DynamicArray.h"
#include<iostream>
#include<cstring>

class Student
{
public:
    Student(std::string name, int age):name(name),age(age){}

    std::string name;
    int age;
};

Student*create(std::string name, int age)
    {
        Student*s = new Student(name,age);
        s->name = name;
        s->age = age;
        return s;
    }

void PrintStu(ElementType ptr)//打印学生信息
    {
        Student *s=(Student*)ptr;
        std::cout <<"姓名:" << s->name << " 年龄:" << s->age << std::endl;
    }

void PrintIndex(ElementType ptr)//打印数组下标
{
    int *index=(int*)ptr;
    std::cout << "下标:"<<*index << std::endl;
}

bool IsStuEqual(ElementType ptr,std::string name, int age)//判断学生是否相等
{
    Student *s=(Student*)ptr;
    if(s->name==name&&s->age==age)
    {
        return true;
    }
    return false;
}

bool SortByName(ElementType ptr1,ElementType ptr2)//按名字排序
{
    Student *s1=(Student*)ptr1;
    Student *s2=(Student*)ptr2;

    return s1->name>s2->name;
}

bool SortByAge(ElementType ptr1,ElementType ptr2)//按年龄排序
{
    Student *s1=(Student*)ptr1;
    Student *s2=(Student*)ptr2;

    return s1->age>s2->age;
}

bool IsDuplicate(ElementType ptr1,ElementType ptr2)//判断是否重复
{
    Student *s1=(Student*)ptr1;
    Student *s2=(Student*)ptr2;

    return s1->name==s2->name&&s1->age==s2->age;
}

bool IsNameEqual(ElementType ptr1, ElementType ptr2)//判断名字是否相同
{
    Student *s1=(Student*)ptr1;
    Student *s2=(Student*)ptr2;

    return s1->name==s2->name;
}

bool MergeByAge(ElementType ptr1,ElementType ptr2)//按年龄合并
{
    Student *s1=(Student*)ptr1;
    Student *s2=(Student*)ptr2;

    return s1->age>=s2->age;
}



/*-------------------------------------------测试函数-------------------------------------------*/
int main()
{
/*-----------------------------------------------------------------------*/
    /*尾插、头插、中间插*/
    // DynamicArray stu;
    // stu.InsertTail(create("zhangsan", 20));//尾插
    // stu.InsertHead(create("lisi", 21));//头插
    // stu.InsertByIndex(1,create("wangwu", 22));//中间插
    // stu.show(PrintStu);//打印
/*-----------------------------------------------------------------------*/
    /*按位置删除*/
    // DynamicArray stu;
    // stu.InsertTail(create("zhangsan", 20));//尾插
    // stu.InsertHead(create("lisi", 21));//头插
    // stu.InsertByIndex(1,create("wangwu", 22));//中间插
    // stu.show(PrintStu);//打印

    // stu.RemoveByIndex(1);//按位置删除
    // stu.show(Print);//打印
/*-----------------------------------------------------------------------*/
     /*按值删除*/
    // DynamicArray stu,S;
    // DynamicArray *Stu;
    // Stu=&stu;
    // stu.InsertTail(create("zhangsan", 20));//尾插
    // stu.InsertHead(create("lisi", 21));//头插
    // stu.InsertByIndex(1,create("wangwu", 22));//中间插
    // stu.show(PrintStu);//打印

    // Student *s=(Student*)S.FindByElement(Stu,"zhangsan", 20,IsStuEqual);
    // stu.RemoveByElement(s);//按值删除
    // stu.show(PrintStu);//打印
/*-----------------------------------------------------------------------*/
    /*按位置查找*/
    // DynamicArray stu;
    // stu.InsertTail(create("zhangsan", 20));//尾插
    // stu.InsertHead(create("lisi", 21));//头插
    // stu.InsertByIndex(1,create("wangwu", 22));//中间插
    // stu.show(PrintStu);//打印
    // ElementType *ptr=stu.FindByIndex(1);//按位置查找
    // PrintStu(*ptr);//打印
/*-----------------------------------------------------------------------*/
    /*按值查找*/
    // DynamicArray stu,S;
    // DynamicArray *Stu;
    // Stu=&stu;
    // stu.InsertTail(create("zhangsan", 20));//尾插
    // stu.InsertHead(create("lisi", 21));//头插
    // stu.InsertByIndex(1,create("wangwu", 22));//中间插
    // stu.show(PrintStu);//打印

    // Student *s=(Student*)S.FindElement(Stu,"zhangsan", 20,IsStuEqual);//按值查找
    // DynamicArray result=stu.FindByElement(s);//按值查找
    // result.show(PrintIndex);//打印
/*-----------------------------------------------------------------------*/
    /*按位置修改*/
    // DynamicArray stu;
    // stu.InsertTail(create("zhangsan", 20));//尾插
    // stu.InsertHead(create("lisi", 21));//头插
    // stu.InsertByIndex(1,create("wangwu", 22));//中间插
    // stu.show(PrintStu);//打印

    // stu.UpdateByIndex(1,create("zhaoliu", 23));//按位置修改
    // stu.show(PrintStu);//打印
/*-----------------------------------------------------------------------*/
    /*按值修改*/
    // DynamicArray stu,S;
    // DynamicArray *Stu;
    // Stu=&stu;
    // stu.InsertTail(create("zhangsan", 20));//尾插
    // stu.InsertHead(create("lisi", 21));//头插
    // stu.InsertByIndex(1,create("wangwu", 22));//中间插
    // stu.show(PrintStu);//打印

    // Student *s=(Student*)S.FindElement(Stu,"zhangsan", 20,IsStuEqual);//按值查找
    // stu.UpdateByElement(s,create("zhaoliu", 23));//按值修改
    // stu.show(PrintStu);//打印
/*-----------------------------------------------------------------------*/
    /*按名字排序*/
    // DynamicArray stu,S;
    // stu.InsertTail(create("zhangsan", 20));//尾插
    // stu.InsertHead(create("lisi", 21));//头插
    // stu.InsertByIndex(1,create("wangwu", 22));//中间插
    // stu.show(PrintStu);//打印

    // stu.Sort(SortByName);//按名字排序
    // stu.show(PrintStu);//打印
/*-----------------------------------------------------------------------*/
    /*按年龄排序*/
    // DynamicArray stu,S;
    // stu.InsertTail(create("zhangsan", 20));//尾插
    // stu.InsertHead(create("lisi", 21));//头插
    // stu.InsertByIndex(1,create("wangwu", 22));//中间插
    // stu.show(PrintStu);//打印

    // stu.Sort(SortByAge);//排序
    // stu.show(PrintStu);//打印
/*-----------------------------------------------------------------------*/
    /*去重算法*/
    // DynamicArray stu;
    // stu.InsertTail(create("zhangsan", 20));//尾插
    // stu.InsertHead(create("lisi", 21));//头插
    // stu.InsertByIndex(1,create("wangwu", 22));//中间插
    // stu.InsertTail(create("lisi", 21));//尾插
    // stu.show(PrintStu);//打印
     
    // stu.Sort(SortByName);//按名字排序
    // stu.show(PrintStu);//打印

    // stu.Duplicate(IsDuplicate);//去重
    // stu.show(PrintStu);//打印
/*-----------------------------------------------------------------------*/
    /*归并算法：合并两个数组已经有序的数列*/
    // DynamicArray stu1,stu2;
    // stu1.InsertTail(create("zhangsan", 20));//尾插
    // stu1.InsertTail(create("lisi", 23));//尾插
    // stu1.InsertTail(create("wangwu", 22));//尾插
    // stu1.Sort(SortByAge);//按年龄排序
    // stu1.show(PrintStu);//打印

    // stu2.InsertTail(create("zhaoliu", 21));//尾插
    // stu2.InsertTail(create("qianqi", 20));//尾插
    // stu2.InsertTail(create("sunba", 24));//尾插
    // stu2.Sort(SortByAge);//按年龄排序
    // stu2.show(PrintStu);//打印

    // DynamicArray stu=stu1.Merge(stu2,MergeByAge);//合并
    // stu.show(PrintStu);//打印
/*-----------------------------------------------------------------------*/
    /*找交集*/
    // DynamicArray stu1,stu2;
    // stu1.InsertTail(create("zhangsan", 20));//尾插
    // stu1.InsertTail(create("lisi", 23));//尾插
    // stu1.InsertTail(create("wangwu", 22));//尾插
    // stu1.Sort(SortByName);//按年龄排序
    // stu1.show(PrintStu);//打印

    // stu2.InsertTail(create("zhangsan", 21));//尾插
    // stu2.InsertTail(create("wangwu", 20));//尾插
    // stu2.InsertTail(create("sunba", 24));//尾插
    // stu2.Sort(SortByName);//按姓名排序
    // stu2.show(PrintStu);//打印

    // DynamicArray stu=stu1.FindInterSection(stu2,IsNameEqual,SortByName);//找交集
    // stu.show(PrintStu);//打印
/*-----------------------------------------------------------------------*/
    /*找并集*/
    // DynamicArray stu1,stu2;
    // stu1.InsertTail(create("zhangsan", 20));//尾插
    // stu1.InsertTail(create("lisi", 23));//尾插
    // stu1.InsertTail(create("wangwu", 22));//尾插
    // stu1.Sort(SortByName);//按姓名排序
    // stu1.show(PrintStu);//打印

    // stu2.InsertTail(create("zhangsan", 21));//尾插
    // stu2.InsertTail(create("wangwu", 20));//尾插
    // stu2.InsertTail(create("sunba", 24));//尾插
    // stu2.Sort(SortByName);//按年龄排序
    // stu2.show(PrintStu);//打印

    // DynamicArray stu=stu1.FindUnionSection(stu2,IsNameEqual,SortByName);//找并集
    // stu.show(PrintStu);//打印
/*-----------------------------------------------------------------------*/
    /*找补集*/
    // DynamicArray stu1,stu2;
    // stu1.InsertTail(create("zhangsan", 20));//尾插
    // stu1.InsertTail(create("lisi", 23));//尾插
    // stu1.InsertTail(create("wangwu", 22));//尾插
    // stu1.Sort(SortByName);//按姓名排序
    // stu1.show(PrintStu);//打印

    // stu2.InsertTail(create("zhangsan", 21));//尾插
    // stu2.InsertTail(create("wangwu", 20));//尾插
    // stu2.InsertTail(create("sunba", 24));//尾插
    // stu2.Sort(SortByName);//按姓名排序
    // stu2.show(PrintStu);//打印

    // DynamicArray stu=stu1.FindDifferentSection(stu2,IsNameEqual,SortByName);//找补集
    // stu.show(PrintStu);//打印
/*-----------------------------------------------------------------------*/
    /*二分查找*/
    // DynamicArray stu,S;
    // DynamicArray*Stu;
    // Stu=&stu;
    // stu.InsertTail(create("zhangsan", 20));//尾插
    // stu.InsertHead(create("lisi", 21));//头插
    // stu.InsertByIndex(1,create("wangwu", 22));//中间插
    // stu.show(PrintStu);//打印
    
    // Student *s=(Student*)S.FindElement(Stu,"lisi", 21,IsStuEqual);
    // size_t n=stu.BinarySearch(s);
    // if(n==ULONG_MAX)
    //     std::cout<<"没找到"<<std::endl;
    
    // else
    //     std::cout<<n<<std::endl;
/*-----------------------------------------------------------------------*/
    /*查找一个数列是不是子数列*/
    // DynamicArray stu1,stu2;
    // stu1.InsertTail(create("zhangsan", 20));//尾插
    // stu1.InsertTail(create("lisi", 23));//尾插
    // stu1.InsertTail(create("wangwu", 22));//尾插
    // stu1.Sort(SortByName);//按姓名排序
    // stu1.show(PrintStu);//打印

    // stu2.InsertTail(create("zhangsan", 21));//尾插
    // stu2.InsertTail(create("wangwu", 22));//尾插
    // stu2.Sort(SortByName);//按姓名排序
    // stu2.show(PrintStu);//打印

    // bool b=stu1.IsChild(stu2,IsNameEqual);
    // if(b)
    //     std::cout<<"是子数列"<<std::endl;
    // else    
    //     std::cout<<"不是子数列"<<std::endl;
/*-----------------------------------------------------------------------*/
/*查找连续子数列*/
    DynamicArray stu1,stu2;
    stu1.InsertTail(create("zhangsan", 20));//尾插
    stu1.InsertTail(create("lisi", 23));//尾插
    stu1.InsertTail(create("wangwu", 22));//尾插
    stu1.Sort(SortByName);//按姓名排序
    stu1.show(PrintStu);//打印

    stu2.InsertTail(create("zhangsan", 21));//尾插
    stu2.InsertTail(create("lisi", 22));//尾插
    stu2.Sort(SortByName);//按姓名排序
    stu2.show(PrintStu);//打印

    bool b=stu1.IsContinueChild(stu2,IsNameEqual);
    if(b)
        std::cout<<"是连续子数列"<<std::endl;
    else    
        std::cout<<"不是连续子数列"<<std::endl;

    return 0;
}
